Read the original article here.

---

Unveiling the Quine: Self-Replicating Code and Forbidden Knowledge

Welcome, fellow explorers of the computational underworld. You're about to delve into a corner of programming rarely discussed in standard curricula – the realm of self-replicating code. Forget dry lectures; we're talking about programs that generate themselves. This isn't just a party trick; it's a deep dive into the fundamental nature of computation and self-reference. In the context of "The Forbidden Code," understanding Quines reveals how programs can understand and manipulate their own essence, a concept that borders on digital sentience, or at least, profound self-awareness.

The most basic form of self-replication in code is the Quine. It's a program that stands alone, requiring no external help or input, yet its sole purpose is to perfectly reproduce its own source code.

What is a Quine?

Let's start with the core definition:

A quine is a computer program that takes no input and produces a copy of its own source code as its only output.

Think about that for a moment. A program, when run, prints the exact text that is the program itself. No reading files, no user input, no network connection – just the code transforming itself into its printed representation. These fascinating constructs are also known in academic circles as "self-replicating programs," "self-reproducing programs," or "self-copying programs."

Why are these possible? This isn't some programming language quirk; it's a fundamental property of powerful computational systems.

Turing-Complete Language: A programming language or system that can perform any computation that a Turing machine can. Essentially, it's powerful enough to compute anything computable. Most modern programming languages (Python, Java, C++, Ruby, etc.) are Turing-complete.

Quines are possible in any Turing-complete programming language. Their existence is a direct consequence of a powerful theoretical result in computer science called Kleene's recursion theorem.

Kleene's Recursion Theorem: A foundational result in computability theory. Roughly speaking, it states that for any computable function, there exists a program that can compute that function and also has access to its own source code. For Quines, the "function" is the execution environment (interpreting or running the program), and the Quine itself is the program that the environment transforms into an output that is identical to the original program's source. It demonstrates that self-reference is an inherent capability within sufficiently powerful computational systems.

Another way to view a quine is through the lens of fixed points:

Fixed Point: In mathematics and computer science, a fixed point of a function is an input value for which the function's output is the same as the input value itself. For Quines, consider the execution environment (compiler + runtime or interpreter) as a function E that takes a program's source code P as input and produces its output O (O = E(P)). A quine is a program Q such that E(Q) = Q. The program is the fixed point of the execution process.

While academically significant, Quines are also a source of amusement and challenge among programmers. Crafting the shortest possible quine in a given language is a common programming puzzle, pushing the boundaries of syntax and self-reference.

The Name: A Philosophical Nod

The term "quine" wasn't always the standard. It was popularized by Douglas Hofstadter in his influential 1979 book Gödel, Escher, Bach: An Eternal Golden Braid. He named these programs in honor of philosopher Willard Van Orman Quine, whose work extensively explored indirect self-reference and paradoxes.

One famous example of Quine's work that inspired the naming is the self-referential statement known as Quine's paradox:

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

This statement, when analyzed, leads to a contradiction if it's either true or false, highlighting the complexities of self-reference. Hofstadter saw a direct parallel between this philosophical paradox and a program that effectively states "This program, when run, produces itself."

A Brief History of Self-Reproducing Automata

The idea of self-reproducing entities predates digital computers. Mathematician John von Neumann theorized extensively about self-reproducing automata in the 1940s, laying some of the theoretical groundwork that would later apply to computer programs.

In the computing world, discussions of self-reproducing programs appeared in articles like Paul Bratley and Jean Millo's "Computer Recreations: Self-Reproducing Automata" in 1972. The first known program fitting the description of a quine is credited to Hamish Dewar, written in Atlas Autocode at the University of Edinburgh in the 1960s.

While Quines might seem like abstract curiosities, the underlying principle of needing access to source code has appeared in more practical contexts. Notably, the "download source" requirement of the GNU Affero General Public License (AGPL) is said to be based on the idea behind a quine – the program, in a sense, must be able to provide the "source code" that generated its behavior (specifically, the server-side code for a web application).

How to Build a Quine: The Core Techniques

There are several ways to approach writing a quine, each revealing different aspects of language design and self-reference. The most fundamental and theoretically pure method is the "constructive" approach.

Constructive Quines: Building from Within

The general strategy for a "true" constructive quine in almost any language involves two key components working in concert:

1. The Code (C): The instructions that perform the printing.
2. The Data (D): A representation (usually a string or array of characters) of the text of the code (C) and the data (D) combined.

The trick is in how the code uses the data. The code (C) needs to:

• Use the data (D) to print the code part (C). Since D represents the entire source code, including C, this is possible.
• Use the data (D), processed in a specific way, to print a representation of the data itself (D). This is the crucial self-referential step. Usually, this involves taking the string representation of D and formatting it correctly (e.g., putting quotes around it and handling special characters) so that when printed, it looks exactly like the original data D in the source code.

When C prints D (formatted correctly) followed by printing C (using D as its source), the result is the full source code string D.

Let's illustrate with a conceptual Python-like example. Imagine the source code is conceptually structured as:

data = "<the string representation of this entire source code>"
code = """
print("data = " + format(data))
print("code = \"\"\"" + code + "\"\"\"") # This is the tricky part conceptually
# or more commonly, the data string contains the whole source structure
"""
# Actual Python Quine structure:
s = "<the string representation of the line starting with s= and the print line>"
print("s = " + repr(s)) # repr(s) gives the string with quotes and escapes
print("print(\"s = \" + repr(s))")
print("print(s)") # This second print line isn't strictly necessary if repr(s)
                 # includes the structure of the whole thing.
                 # A common minimal Python quine focuses on repr:

A common minimal Python 3 quine that demonstrates the constructive pattern using repr():

s = 's = %r; print(s %% s)'
print(s % s)

• Here, s is the data string. It contains a format specifier %r.
• repr(s) (or %r) evaluates to the string s enclosed in quotes, with necessary escapes.
• s % s performs string formatting. It takes the string s and replaces the %r placeholder with the repr() representation of s.
• The print statement outputs this formatted string.
• The formatted string evaluates to 's = \'s = %r; print(s %% s)\'; print(s % s)'.
• When printed, this is exactly: s = 's = %r; print(s %% s)'; print(s % s), which is the original source code.

Java examples often use a similar principle, storing the source or key parts of it in a string variable and then using print statements to output that string, carefully reconstructing the necessary syntax (like quotation marks and semicolons). The Java 15 text blocks feature mentioned in the source material simplifies the representation of the multi-line source string.

SQL quines exploit SQL syntax, often using a SELECT statement that queries a string representation of the SELECT statement itself, needing careful handling of quotes within quotes.

Eval Quines: Running the Code as Data

Some languages offer a shortcut: the ability to treat a string as executable code and run it. This is often done using functions like eval. Quines can take advantage of this feature, making them appear deceptively simple, though some purists might consider this a less "constructive" approach.

Here's the general idea for an eval quine:

1. Store the program's source code (or a representation of it) in a string variable.
2. Print the source string.
3. Execute the source string using eval or a similar function. Since the source string is the program itself, and the program's job is to print the source string, this second step effectively restarts the process or ensures the output is complete. Often, just evaluating the string is enough if the string itself contains the print command.

Simple eval examples from the source material's concept:

In Ruby:

eval s = 'print "eval s = \'#{s}\'"'

• s = 'print "eval s = \'#{s}\'" assigns the string to s.
• The #{} syntax in Ruby allows expression interpolation within strings. Inside the string, it refers back to the variable s itself.
• eval s executes the string. The string print "eval s = \'#{s}\'" becomes print "eval s = 'print \"eval s = \\'#{s}\''" when # {s} is evaluated, which then prints the original source code.

In Lua:

s = 'print("s = "..string.format("%q", s).."; eval(s))'; eval(s)

• Similar principle: assign string s, format it using %q (which properly quotes and escapes it), concatenate with surrounding code, then eval.

In Python 3.8+:

import sys; s = 'sys.stdout.write(f"import sys; s = {s!r}; sys.stdout.write(f\\"import sys; s = {{s!r}}; eval(s)\\")")'; eval(s) # Note: this example is conceptually similar, but a minimal eval quine might just eval a print statement. A common Python eval quine is even shorter:

A more typical, simpler Python eval quine structure (illustrative):

s="print('s=%r;eval(s)'%s);eval(s)" # Assigns the source string to s
print('s=%r;eval(s)'%s); # Prints the formatted string representation of s, recreating the assignment part
eval(s) # Evaluates the string s, which includes the print statement again, completing the self-replication

While concise, these eval quines rely on a powerful language feature (eval) that might not always be available or desirable in production code, making them a distinct category from the more fundamental constructive quines.

The Gray Areas: "Cheating" Quines

The strict definition of a quine ("takes no input," "produces a copy of its own source code") is crucial. Many programs can print their own source code, but if they rely on external information or exploit specific environmental behaviors that aren't part of the program's explicit construction, they are often considered "cheating" by purists.

Understanding these "forbidden" techniques helps clarify what a true quine is and highlights assumptions we often make about programs.

Self-Evaluation as Output

In certain languages, particularly functional or interactive ones (like Scheme, Lisp dialects, APL), simply typing an expression causes the environment to evaluate and print its value. If the value of an expression happens to be its own source representation, you get a quine-like behavior.

For example, in some environments, entering the number 1 simply outputs 1.

Why is this often considered "cheating"? Because the program 1 isn't actively constructing the output string "1". It's just the default behavior of the environment to print the evaluated result of the single, self-evaluating expression that constitutes the program. A true constructive quine involves code that manipulates data to build the output string.

Empty Quines

An empty source file is a valid program in many languages (like C or various scripting languages). If such a program produces no output, is it a quine? It technically produces a copy of its own source code (an empty string) as its output (an empty string).

This clever exploit won the "worst abuse of the rules" prize in the International Obfuscated C Code Contest (IOCCC). The entry wasn't compiled and run to produce an empty file (which is trivial). Instead, the judging script might have copied the empty source file, and the "execution" then consisted of checking the content of the copied file, which was identical to the source. It played on the interpretation of "produces a copy."

While technically meeting a minimalist interpretation, it bypasses the fascinating challenge of computational self-representation that defines a typical quine. Producing no output is less interesting than producing a complex string that mirrors the source code.

Source Code Inspection (Reading Your Own File)

This is perhaps the most common form of "cheating." It's trivial to write a script that opens its own source file, reads its content, and prints it.

#!/bin/bash
cat $0

This shell script works perfectly: $0 refers to the name of the script file, and cat prints its content.

Why is this not a quine? Because it violates the "takes no input" rule. Reading a file, even your own source file, is a form of input from the file system. A true quine must generate its output solely from the information contained within its own source code as interpreted by the language's execution rules, not by accessing external resources.

A slightly shorter variant often seen:

#!/bin/cat

This exploits the shebang line. The kernel executes /bin/cat and passes the script file itself as an argument to cat. Again, this relies on the file system and kernel behavior, acting as input to cat, not the script generating its own source from within its execution logic alone.

Exploiting Environment Messages

Another "forbidden" technique involves triggering error messages or debugger output that happens to print the source code or a relevant part of it. For example, in old GW-BASIC environments, typing Syntax Error caused the interpreter to print the string "Syntax Error". A program consisting solely of Syntax Error might be considered a quine by someone bending the rules, but it relies on the interpreter's specific error handling output, not the program constructing its source text.

Visual or Syntactic Tricks

Sometimes quine-like structures are used for visual effect or obfuscation rather than strict self-replication. The example from Yars' Revenge (an old Atari game) is mentioned as using quine code visually. This likely means a code structure that, when interpreted visually or perhaps due to quirks of the environment, happens to resemble or contain the source code in some non-standard way, potentially combined with "syntactic saccharin" (syntax that is valid but doesn't affect execution) to make the code hard to read. This leans more towards code art or obfuscation than a pure self-replicating program.

Beyond the Quine: Ouroboros Programs and Multiquines

The self-replicating concept can be extended to create even more complex, multi-layered structures.

Ouroboros Programs (Quine Relays)

Named after the ancient symbol of a serpent eating its own tail, an Ouroboros program is a sequence of programs in different languages, where the first program outputs the source code of the second, the second outputs the source code of the third, and so on, until the last program in the sequence outputs the source code of the first program, closing the loop.

Example structure: Program A (in Language X) -> outputs source code of Program B (in Language Y) Program B (in Language Y) -> outputs source code of Program C (in Language Z) ... Program Z (in Language W) -> outputs source code of Program A (in Language X)

The source article mentions several examples of such relay chains, some spanning many languages:

• Haskell -> Python -> Ruby
• C -> Haskell -> Python -> Perl
• A massive relay involving 128 languages from Ruby to Rexx.

These programs are significantly more complex to write than a simple quine, requiring deep understanding of string formatting, escaping, and the specific syntax requirements across multiple languages.

Multiquines

A multiquine takes the multi-language idea in a different direction. It's a set of programs in different languages, where each program in the set is capable of printing the source code of any other program in the set (including itself) when given a specific command-line argument.

As defined by David Madore (creator of the Unlambda language):

"A multiquine is a set of r different programs (in r different languages – without this condition we could take them all equal to a single quine), each of which is able to print any of the r programs (including itself) according to the command line argument it is passed. (Cheating is not allowed: the command line arguments must not be too long – passing the full text of a program is considered cheating)."

Let's break down a 2-language multiquine (biquine):

• You have Program X (in Language A) and Program Y (in Language B).
• Running Program X without an argument outputs the source of Program X (it's a quine in Language A).
• Running Program X with a specific argument (e.g., "Y") outputs the source of Program Y.
• Running Program Y without an argument outputs the source of Program Y (it's a quine in Language B).
• Running Program Y with a specific argument (e.g., "X") outputs the source of Program X.

Essentially, each program in the set acts as a "printer" for the entire set, using a small command-line argument to select which set member to print. This is distinct from an Ouroboros program, where each program only prints the next program in the cycle.

Multiquines exist for many languages, including a 5-part one (Python, Perl, C, NewLISP, F#) and an even larger 25-language version.

Polyglots: Not Always Self-Replicating

Closely related but fundamentally different from multiquines is the concept of a polyglot program.

Polyglot Program: A computer program or script that is simultaneously valid and executable in multiple programming languages or file formats, often producing different results or behaving differently depending on the language used to interpret or execute it.

A key distinction: polyglots are not required to be self-reproducing. Their trick lies in exploiting the differences and overlaps in the syntax of multiple languages. A single file might contain code that is ignored as a comment in one language but is executable code in another, or syntax that has completely different meanings in different languages.

While a polyglot can also be a quine in one or more of the languages it's valid in, the polyglot property itself (being valid syntax in multiple languages) does not stem from Kleene's recursion theorem like the quine property does. Polyglots rely on the specific accidents of syntax, while quines rely on a provable property of computation itself.

Extreme Quines: Radiation Hardening

Pushing the concept further, programmers have created "radiation-hardened" quines.

Radiation-Hardened Quine: A quine that is designed to remain a functional quine even if a single character anywhere in its source code is removed.

These are incredibly difficult to write and, as the name suggests, are inspired by the idea of making code resilient to single-bit errors, like those caused by cosmic rays ("radiation"). The redundancy and self-repairing logic required makes their structure significantly more convoluted than standard quines. The source mentions a Ruby example, which would necessarily involve complex string formatting and logic to account for the potential absence of any given character.

Automatic Generation

Given the theoretical basis in fixed points and recursion theorems, it's perhaps not surprising that creating quines can, in some cases, be automated. Techniques from relational programming can be used.

Relational Programming: A programming paradigm where programs define relationships between inputs and outputs, rather than a direct sequence of computations. The system can then work forwards (find outputs from inputs) or backwards (find inputs from desired outputs). Prolog is a well-known relational language.

By representing the interpreter or compiler of a language as a set of relations, one can theoretically use a relational solver to find a program that is a fixed point – i.e., a program whose execution (as defined by the relations) results in the program itself. This transforms the puzzle of writing a quine into a problem of formal logic and automated solving.

Why This Matters (Beyond the Puzzle)

So why bother with these "forbidden" techniques?

1. Deep Language Understanding: Writing a quine forces you to understand exactly how your chosen language handles strings, quoting, escaping, evaluation, and execution flow at a very fundamental level. You must think like the interpreter or compiler.
2. Exploring Self-Reference: Quines are tangible examples of self-reference in computation, connecting programming to concepts in logic, philosophy, and mathematics.
3. Theoretical Foundations: They demonstrate the practical implications of computability theory results like Kleene's recursion theorem.
4. Code Obfuscation & Art: Quine-like structures, ouroboros programs, and polyglots can be used creatively for code art, programming challenges, or even obfuscation (making code intentionally hard to understand).
5. Unconventional Problem Solving: Tackling the quine challenge requires thinking outside the box, finding clever ways to encode and decode information within the program's own text.

While you won't likely write a quine in your daily job (unless it's for a very specific, niche purpose like code generation or theoretical work), the skills and understanding gained from trying to write one, or studying how they work, are invaluable. They break you out of typical coding patterns and show you the elegant, sometimes paradoxical, power hidden within the languages we use every day. Consider them a rite of passage into the deeper mysteries of code.